1052. 爱生气的书店老板【中等】

• 1. 📝 题目描述
• 2.
• 3. 🎯 s.1 - 滑动窗口
• 4. 🎯 s.2 - 解法 2
• 5. 🎯 s.3 - 解法 3

1. 📝 题目描述

• leetcode

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意。

2.

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

---

提示：

• n == customers.length == grumpy.length
• 1 <= minutes <= n <= 2 * 10^4
• 0 <= customers[i] <= 1000
• grumpy[i] == 0 or 1

3. 🎯 s.1 - 滑动窗口

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} customers
 * @param {number[]} grumpy
 * @param {number} minutes
 * @return {number}
 */
var maxSatisfied = function (customers, grumpy, minutes) {
  const n = customers.length
  let base = 0
  for (let i = 0; i < n; i++) {
    if (grumpy[i] === 0) base += customers[i]
  }
  let extra = 0
  for (let i = 0; i < minutes; i++) {
    if (grumpy[i] === 1) extra += customers[i]
  }
  let maxExtra = extra
  for (let i = minutes; i < n; i++) {
    if (grumpy[i] === 1) extra += customers[i]
    if (grumpy[i - minutes] === 1) extra -= customers[i - minutes]
    maxExtra = Math.max(maxExtra, extra)
  }
  return base + maxExtra
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

算法思路：

• 先统计老板不生气时的基础满意度 base
• 用滑动窗口找出老板抑制情绪 minutes 分钟能额外恶复的最大客户数 maxExtra
• 窗口内只统计老板原本生气的时段（grumpy[i] === 1）的客户数

4. 🎯 s.2 - 解法 2

js

// todo

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

5. 🎯 s.3 - 解法 3

js

// todo

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$